[Coding042] LeetCode 71

Simplify Path

More coding records

Get the knowledge flowing and circulating! :)

目录

※ 本题收获

小知识收获：栈的for循环遍历 | StringBuffer | String字符串的判等

思路收获：一开始写这道题的时候，就按照常规思路来思考，/的处理给我带了很大的困扰，然后按照测试样例逐步完善了我的思路。最后还是没能写出代码。看了以前的程序发现处理/的思维是：既然每层之间都要有/，不防把文件名取出，特判处理., ..的情况，最后在输出答案的时候人为地在目录之间加上/即可。

大大简化了问题，最后得到了答案。很棒！

题目：71. Simplify Path

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:

• The path starts with a single slash '/'.

• Any two directories are separated by a single slash '/'.

• The path does not end with a trailing '/'.

• The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

Example 1:

xxxxxxxxxx
3
1
Input: path = "/home/"
2
Output: "/home"
3
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

xxxxxxxxxx
3
1
Input: path = "/../"
2
Output: "/"
3
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

Example 3:

xxxxxxxxxx
3
1
Input: path = "/home//foo/"
2
Output: "/home/foo"
3
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Constraints:

• 1 <= path.length <= 3000

• path consists of English letters, digits, period '.', slash '/' or '_'.

• path is a valid absolute Unix path.

代码1（配 · 手绘过程图）

xxxxxxxxxx
43
1
class Solution {
2
    public String simplifyPath(String path) {
3
        
4
        String[] seg = path.split("/");
5
        Stack<String> stack = new Stack();
6

7
        for(String s : seg)
8
        {
9
            // System.out.println("-->:|" + s + "|");
10
            
11
            // 判断字符串是否相等，用的是equals()方法，不要用"=="
12
            if (s == "" || s.equals(".")) 
13
            {
14
                continue;
15
            }
16
            
17

18
            if (s.equals(".."))
19
            {
20
                if (stack.size() > 0)
21
                {
22
                    stack.pop();
23
                }
24
            }
25
            else
26
            {
27
                stack.push(s);
28
            }
29
        }
30

31
        StringBuilder result = new StringBuilder();
32
        
33
        // 用这种for循环遍历的方式可以从Stack里把栈底到栈顶的元素打出来~
34
        for (String dir : stack)
35
        {
36
            result.append("/");  // StringBuilder对象有append()方法
37
            result.append(dir);
38
        }
39

40
        // StringBuilder对象有toString()方法
41
        return result.length() > 0 ? result.toString() : "/";
42
    }
43
}

代码解读 | 评价

这个代码写起来还是比较难的，把问题复杂化了。

但是一点点的测试样例让自己的思维越来越丰富，可以明显的发现自己的逻辑思考能力有了些提升。

复杂度分析

代码2（配 · 手绘过程图）

xxxxxxxxxx
34
1
class Solution {
2
    public String simplifyPath(String path) {
3
        
4
        String[] seg = path.split("/");
5
        Stack<String> stack = new Stack();
6

7
        for(String s : seg)
8
        {
9
            if (s.equals(".."))
10
            {
11
                if (!stack.empty())
12
                {
13
                    stack.pop();
14
                }
15
            }
16
            else if (!s.equals(".") && !s.equals(""))
17
            {
18
                stack.push(s);
19
            }
20
            // 这里还有个else，但是不用写了，因为什么都不执行，下一轮循环默认忽略了
21
            // 不添加到栈里，也不pop任何一个栈内元素
22
        }
23

24
        StringBuilder result = new StringBuilder();
25

26
        for (String dir : stack)
27
        {
28
            result.append("/");
29
            result.append(dir);
30
        }
31

32
        return result.length() > 0 ? result.toString() : "/";
33
    }
34
}

代码解读 | 评价

• 代码2比代码1更简洁；

• 代码2更能磨练一个人的思维，更清晰；

复杂度分析

测试样例

• "/home/"

  • "/home"

• "/../"

  • "/"

• "/home//foo/"

  • "/home/foo"

• "/.././../"

  • "/"

• "/a/b/../c/"

  • "/a/c"

• "/a/./b/../../c/"

  • "/c"

• "/././a/b/c/"

  • "/a/b/c"

★ 知识点积累 (Java)

1. 字符串分割

   xxxxxxxxxx
   1
   1
    String[] seg = path.split("/");
   

2. 判断字符串相等

   xxxxxxxxxx
   5
   1
   // 判断字符串是否相等，用的是equals()方法，不要用"=="
   2
   if (s == "" || s.equals(".")) 
   3
   {
   4
       continue;
   5
   }
   

3. StringBuffer

   xxxxxxxxxx
   11
   1
   StringBuilder result = new StringBuilder();
   2
           
   3
   // 用这种for循环遍历的方式可以从Stack里把栈底到栈顶的元素打出来~
   4
   for (String dir : stack)
   5
   {
   6
       result.append("/");  // StringBuilder对象有append()方法
   7
       result.append(dir);
   8
   }
   9
   
   10
   // StringBuilder对象有toString()方法
   11
   return result.length() > 0 ? result.toString() : "/";  // 条件表达式